// 51. N 皇后

package LeetcodeHot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

// import java.beans.beancontext.BeanContext;
// import java.util.ArrayList;
// import java.util.List;

// public class Solution051 {
//     List<List<String>> result = new ArrayList<>();

//     public List<List<String>> solveNQueens(int n) {
//         char[][] chessboard = new char[n][n];
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < n; j++) {
//                 chessboard[i][j] = 'x'; // 'x' 表示可以作为 Q 的候选
//             }
//         }

//         BackTrace(n, chessboard, 0);
//         return result;
//     }

//     private void BackTrace(int n, char[][] chessboard, int num) {
//         // 是否存在空余位置放置Q
//         boolean flag = false;
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < n; j++) {
//                 if (chessboard[i][j] == 'x')
//                     flag = true;
//             }
//         }

//         // 没有空余位置，并且 Q 放完了，则保存结果
//         if (flag == false && num == n) {
//             // 获取当前结果
//             List<String> cb = new ArrayList<>();
//             for (int i = 0; i < n; i++) {
//                 StringBuilder sb = new StringBuilder();
//                 for (int j = 0; j < n; j++) {
//                     sb.append(chessboard[i][j]);
//                 }
//                 cb.add(sb.toString());
//             }
//             boolean isSame = false;
//             for (List<String> list : result) {
//                 boolean isSameforlist = true;
//                 for (int i = 0; i < n; i++) {
//                     isSameforlist = isSameforlist && (list.get(i).equals(cb.get(i)));
//                 }
//                 if (isSameforlist == true) {
//                     isSame = true;
//                     break;
//                 }
//             }
//             if (!isSame)
//                 result.add(new ArrayList<>(cb));
//         }

//         // 没有空余位置，并且 Q 不足，则结果错误
//         if (flag == false && num < n)
//             return;

//         // 随机选择位置放置 Q
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < n; j++) {
//                 if (chessboard[i][j] == 'x') {
//                     // 拷贝棋盘
//                     char[][] cp = new char[n][n];
//                     for (int x = 0; x < n; x++) {
//                         for (int y = 0; y < n; y++) {
//                             cp[x][y] = chessboard[x][y];
//                         }
//                     }
//                     // 放置 Q
//                     chessboard[i][j] = 'Q';
//                     // 横竖和斜边设置为 .
//                     // 横竖
//                     for (int k = 0; k < n; k++) {
//                         if (chessboard[i][k] == 'x')
//                             chessboard[i][k] = '.';
//                         if (chessboard[k][j] == 'x')
//                             chessboard[k][j] = '.';
//                     }

//                     // 斜边
//                     for (int x = 0; x < n; x++) {
//                         for (int y = 0; y < n; y++) {
//                             if ((x + y == i + j) && chessboard[x][y] == 'x')
//                                 chessboard[x][y] = '.';
//                             if ((x - y == i - j) && chessboard[x][y] == 'x')
//                                 chessboard[x][y] = '.';
//                         }
//                     }
//                     BackTrace(n, chessboard, num + 1);
//                     // 回溯
//                     for (int x = 0; x < n; x++) {
//                         for (int y = 0; y < n; y++) {
//                             chessboard[x][y] = cp[x][y];
//                         }
//                     }
//                 }
//             }
//         }
//     }
// }

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<List<String>>();
        // queens 数组用于保存皇后的位置，index 表示 Q 的行， value 表示 Q 的列
        int[] queens = new int[n]; 
        Arrays.fill(queens, -1);
        // 当前已经有 Q 的列号
        Set<Integer> columns = new HashSet<Integer>(); 
        // 当前已经有 Q 的右斜边， 每条右斜边 i - j 的值是唯一的
        Set<Integer> diagonals1 = new HashSet<Integer>(); 
        // 当前已经有 Q 的左斜边， 每条右斜边 i + j 的值是唯一的
        Set<Integer> diagonals2 = new HashSet<Integer>(); 
        backTrace(result, queens, n, 0, columns, diagonals1, diagonals2);
        return result;
    }

    public void backTrace(List<List<String>> result, int[] queens, int n, int row, Set<Integer> columns,
            Set<Integer> diagonals1, Set<Integer> diagonals2) {
        // 如果每一行都成功放置了皇后，则添加到最后的结果中
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            result.add(board);
        } else {
            // 如果第 row 行没有放置皇后，则遍历每一列，选择每个可以放置的位置
            for (int col = 0; col < n; col++) {
                // 判断列和斜边是否重复
                if (columns.contains(col)) {
                    continue;
                }
                if (diagonals1.contains(row - col)) {
                    continue;
                }
                if (diagonals2.contains(row + col)) {
                    continue;
                }
                // 对于可以选择的位置进行递归
                queens[row] = col;
                columns.add(col);
                diagonals1.add(row - col);
                diagonals2.add(row + col);
                backTrace(result, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(col);
                diagonals1.remove(row - col);
                diagonals2.remove(row + col);
            }
        }
    }

    // 根据 queens 的定义构造棋盘
    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}
